package com.lintcode.solution;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class Solution_4 {
    public static void main(String[] agrs) {
        Solution_4 solution = new Solution_4();
        System.out.println(solution.nthUglyNumber(41));
    }
    
    public int nthUglyNumber(int n) {
        int p2, p3, p5;
        int result;
        p2 = p3 = p5 = 0;
        List<Integer> list = new ArrayList<>();
        list.add(1);
        while (list.size() < n) {
            int a = list.get(p2);
            int b = list.get(p3);
            int c = list.get(p5);
            result = Math.min(Math.min(a * 2, b * 3), Math.min(a * 2, c * 5));
            list.add(result);
            if (result == a * 2) {
                p2++;
            }
            if (result == b * 3) {
                p3++;
            }
            if (result == c * 5) {
                p5++;
            }
            System.out.println(a + "," + b + "," + c + "," + result);
        }
        return list.get(list.size() - 1);
    }
}
